home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / language / awe / awe-full.lha / Awe2 / DoNotUseThisSrc / SharedMalloc-real.cc < prev    next >
C/C++ Source or Header  |  1990-08-08  |  10KB  |  412 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. // 
  3. // Copyright (C) 1988 University of Illinois, Urbana, Illinois
  4. //
  5. // written by Dirk Grunwald (grunwald@cs.uiuc.edu)
  6. //
  7. //
  8. // Allocator.c: based loosely on...
  9. //
  10. // malloc.c (Caltech) 2/21/82
  11. // Chris Kingsley, kingsley@cit-20.
  12. //
  13. //    $Header: /foobar/grunwald/Awe2/NewSrc/RCS/SharedMalloc-real.cc,v 4.1 89/10/18 13:28:22 grunwald Exp Locker: grunwald $
  14. //
  15. // This is a very fast storage allocator.  It allocates blocks of a small 
  16. // number of different sizes, and keeps free lists of each size. In this 
  17. // implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  18. // 
  19.  
  20. #define NDEBUG
  21.  
  22.  
  23. #ifdef __GNUG__
  24. #  pragma implementation
  25. #endif
  26.  
  27. #include <stdio.h>
  28. #include <stream.h>
  29. #include "Debug.h"
  30. #include "assert.h"
  31. #include "CpuMultiplexor.h"
  32.  
  33. #ifdef __GNUG__
  34. extern "C" {
  35. #endif
  36.  
  37. void *sbrk(int);
  38. void exit(int x = 0);
  39. void *malloc( unsigned );
  40. void free(void *);
  41. void perror(const char*);
  42.  
  43. #ifdef __GNUG__
  44. };
  45. #endif
  46.  
  47. const int NOTREACHED = 0;
  48.  
  49. extern int CpuMuxDebugFlag;
  50.  
  51. //
  52. //    calloc and cfree are defined in terms of malloc.
  53. //    alloca allocates space from the current stack.
  54. //
  55.  
  56. #include "assert.h"
  57. #include "SpinLock.h"
  58.  
  59. //
  60. // Allocator.h: based loosely on...
  61. //
  62. // malloc.c (Caltech) 2/21/82
  63. // Chris Kingsley, kingsley@cit-20.
  64. //
  65. //    $Header: /foobar/grunwald/Awe2/NewSrc/RCS/SharedMalloc-real.cc,v 4.1 89/10/18 13:28:22 grunwald Exp Locker: grunwald $
  66. //
  67. // 
  68.  
  69. //
  70. // Below is a allocator sbuclass based loosely on..
  71. //
  72. // malloc.c (Caltech) 2/21/82
  73. // Chris Kingsley, kingsley@cit-20.
  74. //
  75. // This is a very fast storage allocator.  It allocates blocks of a small 
  76. // number of different sizes, and keeps free lists of each size. In this 
  77. // implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  78. // 
  79.  
  80. //
  81. // The overhead on a block is at least 4 bytes.  When free, this space
  82. // contains a pointer to the next free block, and the bottom two bits must
  83. // be zero.  When in use, the first byte is set to MAGIC, and the second
  84. // byte is the size index.  The remaining bytes are for alignment.
  85. // If range checking is enabled and the size of the block fits
  86. // in two bytes, then the top two bytes hold the size of the requested block
  87. // plus the range checking words, and the header word MINUS ONE.
  88. // 
  89. union    overhead {
  90.     union    overhead * ov_next;    // when free
  91.     struct {
  92.     unsigned char    ovu_magic;    // magic number
  93.     unsigned char    ovu_index;    // bucket #
  94.     unsigned short    ovu_size;    // actual block size
  95.     unsigned int    ovu_rmagic;    // range magic number
  96.     } ovu;
  97. };
  98.  
  99. #define    ov_magic    ovu.ovu_magic
  100. #define    ov_index    ovu.ovu_index
  101. #define    ov_size        ovu.ovu_size
  102. #define    ov_rmagic    ovu.ovu_rmagic
  103.  
  104. #define    MAGIC        0xff        /* magic # on accounting info */
  105. #define RMAGIC        0x55555555    /* magic # on range info */
  106. #define    RSLOP        sizeof( unsigned int )
  107.  
  108. //
  109. // nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  110. // smallest allocatable block is 8 bytes.  The overhead information
  111. // precedes the data area returned to the user.
  112. // 
  113.  
  114. int const NumberOfBuckets = 30;
  115.  
  116. class BucketAllocator {
  117. protected:
  118.     union overhead * nextf[ NumberOfBuckets ];
  119.     SpinLock bucketLock[ NumberOfBuckets ];
  120.     
  121.     SpinLock topLock;
  122.     char * top;
  123.  
  124.     char sbrkDisabled;
  125.     char initialized;
  126.     
  127.     int morecore( int bucket );
  128.  
  129.     void initialize();
  130. public:
  131.     BucketAllocator();
  132.     ~BucketAllocator();
  133.     void * allocate( unsigned nbytes );
  134.     void free( void * cp );
  135.     void disableFurtherBreaks();
  136. };
  137.  
  138. BucketAllocator HardwareMemoryAllocator;
  139.  
  140. BucketAllocator::BucketAllocator()
  141. {
  142.     initialize();
  143. }
  144.  
  145. void
  146. BucketAllocator::disableFurtherBreaks()
  147. {
  148.     sbrkDisabled = 1;
  149. }
  150.  
  151. void disableFurtherBreaks()
  152. {
  153.     HardwareMemoryAllocator.disableFurtherBreaks();
  154. }
  155.  
  156. void
  157. BucketAllocator::initialize()
  158. {
  159.     if (initialized) return;
  160.     //
  161.     // First allocate the state information for the object from the
  162.     // sourceMemoryObjectCache.
  163.     // 
  164.  
  165.     for( int i = 0; i < NumberOfBuckets; i++ ) {
  166.     nextf[ i ] = 0;
  167.     }
  168.     
  169.     extern int end;
  170.     top = (char *) &end;
  171.     sbrkDisabled = 0;
  172.     initialized = 1;
  173. }
  174.  
  175. //
  176. //    Deleteing the allocator doesn't free up your memory, it just
  177. //    makes us forget about it. However, this is only done when
  178. //    you call exit, so who cares.
  179. //
  180. BucketAllocator::~BucketAllocator()
  181. {
  182. }
  183.  
  184. void *
  185. BucketAllocator::allocate( unsigned nbytes )
  186. {
  187.     if (!initialized) {
  188.     initialize();
  189.     }
  190.  
  191.     union overhead * p;
  192.     int bucket = 0;
  193.     unsigned shiftr;
  194.  
  195. #ifndef NDEBUG    
  196.     if (CpuMuxDebugFlag) {
  197.     cerr << "BucketAllocator::allocate( " << nbytes;
  198.     cerr << " ) for top = " << hex(long(top)) << "\n";
  199.     }
  200. #endif
  201.     //
  202.     // Convert amount of memory requested into
  203.     // closest block size stored in hash buckets
  204.     // which satisfies request.  Account for
  205.     // space used per block for accounting.
  206.     // 
  207.     nbytes += sizeof( union overhead ) + RSLOP;
  208.     nbytes = ( nbytes + 3 ) &~ 3; 
  209.     shiftr = ( nbytes - 1 ) >> 2;
  210.     // apart from this loop, this is O(1) */
  211.      while( shiftr >>= 1 )
  212.      bucket++;
  213.     
  214.     Debug( "BucketAllocator::allocate: nbytes=%x, shiftr=%x, bucket=%x\n",
  215.       nbytes, shiftr, bucket );
  216.     assert( bucket < NumberOfBuckets );
  217.     
  218.     //
  219.     // If nothing in hash bucket right now, request more memory from
  220.     // the system.
  221.     // This is probably pathalogical (?) and can lead to one processor
  222.     // always allocation memory for everybody else, but hopefully the
  223.     // locks will make it somewhat fairer.
  224.     // 
  225.     Debug( "BucketAllocator::allocate: waiting on bucket %d lock\n",
  226.       bucket );
  227.     bucketLock[bucket].reserve();
  228.     while( nextf[ bucket ] == 0 ) {
  229.     Debug( "BucketAllocator::allocate: filling bucket %d\n",
  230.           bucket );
  231.     bucketLock[bucket].release();
  232.     if( ! morecore( bucket ) )
  233.         break;
  234.     bucketLock[bucket].reserve();
  235.     }
  236.     Debug( "BucketAllocator::allocate: nextf[bucket] = %x\n",
  237.       nextf[bucket] );
  238.     if( nextf[bucket] == 0 ) {
  239.     fprintf(stderr, "BucketAllocator::allocate REALLY out of memory\n" );
  240.     bucketLock[bucket].release();
  241.     return( 0 );
  242.     }
  243.     
  244.     //
  245.     // Grab the next entry in the bucket.
  246.     // 
  247.     p = nextf[ bucket ];
  248.     Debug( "BucketAllocator::allocate: p = %x\n", p );
  249.     
  250.     //
  251.     // remove from linked list
  252.     // 
  253.     nextf[ bucket ] = nextf[ bucket ]->ov_next;
  254.     bucketLock[bucket].release();
  255.     
  256.     p->ov_magic = MAGIC;
  257.     p->ov_index= bucket;
  258.     
  259.     //
  260.     // Record allocated size of block and
  261.     // bound space with magic numbers.
  262.     // 
  263.     if( nbytes <= 0x10000 )
  264.     p->ov_size = nbytes - 1;
  265.     p->ov_rmagic = RMAGIC;
  266.     *((unsigned int *) ((char *) p + nbytes - RSLOP)) = RMAGIC;
  267.     
  268.     Debug( "BucketAllocator::allocate: returning %A\n", (char *) (p + 1) );
  269.     return( (char *) (p + 1) );
  270. }
  271.  
  272. //
  273. // Get more memory into a bucket. Also prefetch the memory.
  274. // 
  275. int
  276. BucketAllocator::morecore( int bucket )
  277. {
  278.     union overhead * op;
  279.     int rnu;       // 2^rnu bytes will be requested
  280.     int nblks;     // become nblks blocks of the desired size
  281.     int siz;
  282.     
  283.     Debug( "BucketAllocator::morecore( bucket:%d )\n", bucket );
  284.     
  285.     //
  286.     // take PAGESIZE (4k) unless the block is bigger than that
  287.     //
  288.     
  289.     rnu = ( bucket <= 9 ) ? 12 : bucket + 3;
  290.     nblks = 1 << ( rnu - ( bucket + 3 ) );  // how many blocks to get
  291.     if( rnu < bucket )
  292.     rnu = bucket;
  293.     
  294.     Debug( "BucketAllocator::morecore(): getting %d bytes\n", 1 << rnu );
  295.     
  296.     //
  297.     // See if there is room left in the cached space for the request.
  298.     // 
  299.     topLock.reserve();
  300.     int nbytes = 1 << rnu;
  301.     
  302.     char *highest = (char *) sbrk(0);
  303.     
  304.     if ( ( top + nbytes ) > highest ) {
  305.     if ( sbrkDisabled ) {
  306.  
  307.         cerr << "BucketAllocator::morecore: out of memory\n";
  308.         cerr << "top     = " << hex(long(top)) << "\n";
  309.         cerr << "highest = " << hex(long(highest)) << "\n";
  310.         cerr << "sbrk(0) = " << hex(long(sbrk(0))) << "\n";
  311.  
  312.         topLock.release();
  313.  
  314.         return( 0 );
  315.     }
  316.     else {
  317.         //
  318.         //    Get more space & reduce the number of system calls.
  319.         //
  320.         highest = (char *) sbrk(nbytes * 2);
  321.     }
  322.     }
  323.     
  324.     op = (union overhead *) top;
  325.     top += nbytes;
  326.     topLock.release();
  327.     //
  328.     // Round up to minimum allocation size boundary
  329.     // and deduct from block count to reflect.
  330.     // 
  331.     if( (int) op & 7 ) {
  332.     op = (union overhead *) (((int)op + 8) &~ 7);
  333.     nblks--;
  334.     }
  335.     Debug( "BucketAllocator::morecore(): adjusted op = %x\n", op );
  336.     
  337.     //
  338.     // Add new memory allocated to that on
  339.     // free list for this hash bucket.
  340.     // 
  341.     siz = 1 << ( bucket + 3 );
  342.     
  343.     union overhead * block = op;
  344.     
  345.     Debug( "BucketAllocator::morecore(): nblks = %d  size = %d\n",
  346.       nblks, siz );
  347.     while( --nblks > 0 ) {
  348.     block->ov_next = (union overhead *) ( (char *) block + siz );
  349.     block = (union overhead *) ( (char *) block + siz );
  350.     }
  351.     Debug( "BucketAllocator::morecore(): adding new memory to bucket %d\n",
  352.       bucket );
  353.     
  354.     bucketLock[bucket].reserve();
  355.     
  356.     block->ov_next = nextf[ bucket ];    // terminate the list with
  357.     // anything that was already 
  358.     // there..
  359.     nextf[ bucket ] = op;
  360.     
  361.     bucketLock[bucket].release();
  362.     return( 1 );
  363. }
  364.  
  365. //
  366. // Return memory to the free pool.
  367. // Currently this does not return the physical pages associated with the
  368. // memory, but it should.
  369. // 
  370. void
  371. BucketAllocator::free( void * cp )
  372. {   
  373.     int bucket;
  374.     union overhead *op;
  375.     
  376.     Debug( "BucketAllocator::free( %x )\n", cp );
  377.     if( cp == 0 )
  378.     return;
  379.     op = (union overhead *) ( (char *) cp - sizeof( union overhead ) );
  380.  
  381.     assert( op->ov_magic == MAGIC );    // make sure it was in use
  382.     assert( op->ov_rmagic == RMAGIC );
  383.  
  384.     if( op->ov_index <= 13 )
  385.     assert( *(unsigned int *)((char *)op + op->ov_size + 1 - RSLOP) == RMAGIC );
  386.  
  387.     assert( op->ov_index < NumberOfBuckets );
  388.     bucket = op->ov_index;
  389.     bucketLock[bucket].reserve();
  390.     op->ov_next = nextf[ bucket ];
  391.     nextf[ bucket ] = op;
  392.     bucketLock[bucket].release();
  393. }
  394.  
  395. #ifdef __GNUG__
  396. extern "C" void *malloc( unsigned size)
  397. #else
  398. void *malloc( unsigned size)
  399. #endif
  400. {
  401.     return( ( void * )HardwareMemoryAllocator.allocate( size ) );
  402. }
  403.  
  404. #ifdef __GNUG__
  405. extern "C" void free(void * ptr)
  406. #else
  407. void free(void * ptr)
  408. #endif
  409. {
  410.     HardwareMemoryAllocator.free( (void *) ptr );
  411. }
  412.